package com.xufx.algorithm.string;

/**
 * leetcode 5 longest palindromic substring
 * @link https://leetcode.cn/problems/longest-palindromic-substring/description/
 * describe: Given a string s, return the longest palindromic substring in s.
 * example :
 *  Input : s = "babad"
 *  OutPut: "bab"
 *  Explanation: "aba" is also a valid answer
 */
public class Leetcode5LongestPalindromicSubstring {

    public static void main(String[] args) {
        String s = "babad";
        System.out.println(longestPalindRome(s));
    }

    /**
     * 时间复杂度 O(n * n)
     */
    private static String longestPalindRome(String s){
        // 字符串问题的小技巧 --> 先转换成char数组
        char[] ss = s.toCharArray();
        int len = ss.length;
        String res = "";
        // 处理特殊情况
        if (len == 0 || len == 1){
            return s;
        }

        for (int i = 0; i < len; i++){
            // 最精彩的来了，判断回文串的经典方法
            // 1. 先处理奇数回文串
            int j = i;
            int k = i;
            while(j >= 0 && k < len && ss[k] == ss[j]){
                if(k - j + 1 >= res.length()){
                    res = s.substring(j, k + 1);
                }
                // j 向前， k向后
                j --;
                k ++;
            }
            // 2. 再处理偶数回文串
            j = i;
            k = i + 1;
            while(j >= 0 && k < len && ss[k] == ss[j]){
                if(k - j + 1 >= res.length()){
                    res = s.substring(j, k + 1);
                }
                // j 向前， k向后
                j --;
                k ++;
            }
        }
        return res;
    }
}
